package com.beikai.demo01.sort.impl;

import com.beikai.demo01.sort.ArrSort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @author : hanbeikai
 * Date: 2021/6/4 7:50 下午
 * Description: 归并排序
 * 归并算法采用递归的方式进行,使用的是分治的理念,
 * 1. 拆分数组为两个
 * 2. 然后对这两个数组进行比较,较小或较大的放到一个新的数组中,返回排好序的数组
 * <p>
 * 然后1,2不断递归
 */
public class GuiBingSort extends ArrSort {

    @Override
    public int[] sort(int[] arr) {
        // 判断当前的数组是否可以被拆分
        if (arr.length < 2) {
            return arr;
        }

        // 计算中间坐标
        int midIndex = arr.length >> 1;
        // 拆分数组
        int[] left = sort(Arrays.copyOfRange(arr, 0, midIndex));
        int[] right = sort(Arrays.copyOfRange(arr, midIndex, arr.length));

        return handle(left, right);
    }

    /**
     * 排序两个数组
     *
     * @param left
     * @param right
     * @return
     */
    private int[] handle(int[] left, int[] right) {
        // 创建一个容得下两个数组的数组
        int[] ints = new int[left.length + right.length];
        // 设置比较的起点
        int rightIndex = 0;
        int leftIndex = 0;
        int intsIndex = 0;
        // 如果两个数组都没有比较完
        while (rightIndex < right.length && leftIndex < left.length){
            if (right[rightIndex] > left[leftIndex]){
                ints[intsIndex++]=right[rightIndex++];
            }else {
                ints[intsIndex++]=left[leftIndex++];
            }
        }
        // 如果left 数组没有比较完
        while (rightIndex < right.length){
            ints[intsIndex++]=right[rightIndex++];
        }

        // 如果right 数组没有比较完
        while (leftIndex < left.length){
            ints[intsIndex++]=left[leftIndex++];
        }
        return ints;
    }
}
